package mess;

public class LeeCode_21 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        System.out.println(mergeTwoLists(l1, l2));
        ListNode l3 = null;
        ListNode l4 = new ListNode(0);
        System.out.println(mergeTwoLists(l3, l4));
        System.out.println("-------------");
        ListNode l5 = new ListNode(2);
        ListNode l6 = new ListNode(1);
        System.out.println(mergeTwoLists(l5, l6));
    }

    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        int val1 = list1.val;
        int val2 = list2.val;
        ListNode result = null;
        if (val1 <= val2) {
            result = new ListNode(val1);
            digui(list1.next, list2, result);
        }
        else {
            result = new ListNode(val2);
            digui(list1, list2.next, result);
        }
        return result;
    }
    private static void digui (ListNode list1, ListNode list2, ListNode result){
        if (list1 == null){
            result.next = list2;
            return;
        }
        if (list2 == null){
            result.next = list1;
            return;
        }
        System.out.println(result);
        int val1 = list1.val;
        int val2 = list2.val;
        if (val1 <= val2){
            result.next = new ListNode(val1);
            if (list1.next == null){
                result.next.next = list2;
                return;
            }
            digui(list1.next, list2, result.next);
        }
        else{
            result.next = new ListNode(val2);
            digui(list1, list2.next, result.next);
        }
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return this.val + "->" + this.next;
        }
    }
}
